root_path ="D:/recent_arrangement/something_engd/something/桥安开发任务/裂缝论文/crack"
# 添加到sys.path
import sys
if '__file__' in globals():
    sys.path.append(root_path)
import cv2 as cv
import numpy as np
from typing import *
from rtree import index
import itertools
import copy
from crack_lib.utl import *
from crack_lib.crack_struct import *
from sortedcontainers import SortedList

def find_edge_hori(img,bottom,top,start,stride,_min=0,_max=None):
    if _max==None:
        _max=img.shape[1]-1
    cur_pos=start
    find_pixel=True
    if start==0 and stride==-1:
        return 0
    if start==_max and stride==1:
        return _max
    while find_pixel and cur_pos+stride>=_min and cur_pos+stride<=_max:
        cur_pos+=stride
        find_pixel=False
        for i in range(bottom,top+1):
            if(img[i][cur_pos]==1):
                find_pixel=True
                break
    if find_pixel==True:
        return cur_pos
    else :
        return cur_pos-stride
def find_edge_vert(img,left,right,start,stride,_min=0,_max=None):
    if _max==None:
        _max=img.shape[0]-1
    cur_pos=start
    find_pixel=True
    if start==0 and stride==-1:
        return 0
    if start==_max and stride==1:
        return _max
    while find_pixel and cur_pos+stride>=_min and cur_pos+stride<=_max:
        cur_pos+=stride
        find_pixel=False
        for i in range(left,right+1):
            if(img[cur_pos][i]==1):
                find_pixel=True
                break
    if find_pixel==True:
        return cur_pos
    else :
        return cur_pos-stride
def get_tuple_rect(rect:Rect):
    return (rect.p1.x,rect.p1.y,rect.p2.x,rect.p2.y)
def get_bridge_rect(rect1:Rect,rect2:Rect)->Rect:
    x1=max(rect1.p1.x,rect2.p1.x)
    x2=min(rect1.p2.x,rect2.p2.x)  
    interval_x=(x1,x2) if x1<x2 else (x2,x1)
    y1=max(rect1.p1.y,rect2.p1.y)
    y2=min(rect1.p2.y,rect2.p2.y)  
    interval_y=(y1,y2) if y1<y2 else (y2,y1)
    return Rect(Point(interval_x[0],interval_y[0]),Point(interval_x[1],interval_y[1]))

class CrackManager:
    def __init__(self) -> None:
        self.blocks=[]
        self.max_bid=0
        self.cracks=[]
        self.max_cid=0
    def get_bid(self):
        out=self.max_bid
        self.max_bid+=1
        return out
    def get_cid(self):
        out=self.max_cid
        self.max_cid+=1
        return out
    def trim2img(self,rect:Rect):
        img_rect=Rect(Point(0,0),Point(self.bin_img.shape[1]-1,self.bin_img.shape[0]-1))
        return img_rect.rect_and(rect)
    def get_pixel_rect(self,rect:Rect):
        return self.bin_img[int(rect.p1.y):int(rect.p2.y)+1:1,int(rect.p1.x):int(rect.p2.x)+1:1]
    def get_Occupancy(self,rect:Rect):
        pixels=self.get_pixel_rect(rect)
        num_one=np.count_nonzero(pixels)
        num_all=pixels.size
        if num_all==0 :
            print(rect.p1.x,rect.p1.y,rect.p2.x,rect.p2.y)
        occupancy=num_one/num_all
        return occupancy
    def check_bridge(self,rect1,rect2):
        if rect1==rect2:
            return True
        if is_rectangle_overlap(rect1,rect2)==True:
            intersect=rect1.rect_and(rect2)
            intersect_pixel=self.get_pixel_rect(intersect)
            if not (np.any(intersect_pixel==1)):
                return False
            return True
        bridge_rect=get_bridge_rect(rect1,rect2)
        if min(bridge_rect.width,bridge_rect.height)>16:
            return False
        extend_bridge_rect=bridge_rect.extend_abs((4,4),(0,0),self.img.shape).extend((0.3,0.3),(0,0),self.img.shape)
        extend_bridge_rect=self.trim2img(extend_bridge_rect)
        # pixels=self.get_pixel_rect(extend_bridge_rect).reshape(extend_bridge_rect.height,extend_bridge_rect.width)
        # cv.imshow("tmp1",pixels*255)
        # tmp=cluster1.rect()+cluster2.rect()
        # cv.imshow("tmp2",self.get_pixel_rect(tmp).reshape(tmp.height,tmp.width)*255)
        # cv.imshow("tmp3",self.get_pixel_rect(cluster1.rect()).reshape(cluster1.rect().height,cluster1.rect().width)*255)
        # cv.imshow("tmp4",self.get_pixel_rect(cluster2.rect()).reshape(cluster2.rect().height,cluster2.rect().width)*255)
        # cv.waitKey(0)
        # indices = np.where(pixels==1)
        # y_min = np.min(indices[0])+extend_bridge_rect.p1.y
        # y_max = np.max(indices[0])+extend_bridge_rect.p1.y
        # x_min = np.min(indices[1])+extend_bridge_rect.p1.x
        # x_max = np.max(indices[1])+extend_bridge_rect.p1.x
        # pixel_rect=Rect(Point(x_min,y_min),Point(x_max,y_max))
        # extend_pixel_rect=pixel_rect.extend((0.5,0.5))
        overlapping_rect1=extend_bridge_rect.rect_and(rect1)
        overlapping_rect2=extend_bridge_rect.rect_and(rect2)
        #检查该区域是否有像素
        if overlapping_rect1==None or overlapping_rect2==None:
            return False
        overlapping_pixel1=self.get_pixel_rect(overlapping_rect1.extend((0.3,0.3),(0,0),self.img.shape))
        overlapping_pixel2=self.get_pixel_rect(overlapping_rect2.extend((0.3,0.3),(0,0),self.img.shape))
        if not (np.any(overlapping_pixel1==1) and np.any(overlapping_pixel2==1)):
            # return pixel_rect.width<min(cluster1.rect().width,cluster2.rect().width)
            return False
        # print("pass")
        return True
    def encode_crack(self,img_path):
        testimg=cv.imread(img_path,cv.IMREAD_GRAYSCALE)
        self.img=testimg.copy()
        #二值化
        testimg[testimg<=100]=0
        testimg[testimg>100]=1
        self.bin_img=testimg.copy()
        assert len(testimg.shape)==2
        #获取条带
        min_height=16
        h=testimg.shape[0]
        slices_ranges=[(i*min_height,min(i*min_height+min_height-1,h-1)) for i in range((h+min_height-1)//min_height)]
        #计算crack block
        pre_blocks=[]
        for slice_range in slices_ranges:#遍历每一个条带
            intervals=[]
            scan_line1=testimg[slice_range[0]]
            scan_line2=testimg[slice_range[1]]
            scan_line=np.stack([scan_line1,scan_line2],axis=0).transpose()
            pre_pixel=0
            i=0
            while i<len(scan_line):
                pixels=scan_line[i]
                _next=i
            # for i,pixels in enumerate(scan_line):#遍历一条像素
                for pixel in pixels:
                    if(pre_pixel==0 and pixel==1):#找到一个裂缝块
                        #计算interval
                        #找左界
                        left=find_edge_hori(testimg,slice_range[0],slice_range[1],i,-1)
                        right=find_edge_hori(testimg,slice_range[0],slice_range[1],i,1)
                        
                        if left==right:
                            pre_pixel=pixel
                            continue
                        _next=right
                        if(left>right):
                            print("what")
                        #
                        # if len(intervals)==0 or not istouch(intervals[-1],(left,right)):
                        #     intervals.append((left,right))
                        # else :
                        #     last_one=intervals.pop()
                        #     intervals.append(merge(last_one,(left,right)))
                        intervals.append((left,right))#考虑了每次的block的距离后就不用merge了（不会出现重叠的情况）    
                        pass
                    pre_pixel=pixel
                if _next>i:
                    i=_next+1
                else :
                    i=i+1
            #构建block
            blocks=[]
            for interval in intervals:
                block=Block(Point(interval[0],slice_range[0]),Point(interval[1],slice_range[1]),self.get_bid())
                blocks.append(block.bid)
                self.blocks.append(block)
                #检查上下连接情况
                if len(pre_blocks)!=0:
                    for pre_interval_bid in pre_blocks:
                        pre_top_block=self.blocks[pre_interval_bid]
                        pre_interval=pre_top_block.get_hori_range()
                        if(istouch((interval[0]-1,interval[1]+1),pre_interval)):
                            block.bottom_adj.append(pre_interval_bid)
                            pre_top_block.top_adj.append(block.bid)
            pre_blocks=blocks
        #构建crack
        visit=[0 for i in range(len(self.blocks))]
        visit_blocks_quene=[]
        for i in range(len(visit)):
            if visit[i]==0:#访问一个裂缝
                blocks4crack=[]
                cid=self.get_cid()
                visit_blocks_quene.append(self.blocks[i])
                while len(visit_blocks_quene)!=0:
                    cur_block=visit_blocks_quene.pop()
                    visit[cur_block.bid]=1
                    cur_block.cid=cid
                    blocks4crack.append(cur_block)
                    adjs=cur_block.get_adj()
                    for adj in adjs:
                        if visit[self.blocks[adj].bid]==0:
                            visit_blocks_quene.append(self.blocks[adj])
                crack=Crack(blocks4crack,cid)
                self.cracks.append(crack)

        pass
    def encode_crack_raw(self,img_path):#用8连接算法实现裂缝识别
        testimg=cv.imread(img_path,cv.IMREAD_GRAYSCALE)
        self.img=testimg.copy()
        #二值化
        testimg[testimg<=100]=0
        testimg[testimg>100]=255
        assert len(testimg.shape)==2
        nb_labels,labels = cv.connectedComponents(testimg)
        # 保存每个区域的包围盒
        boxes = []
        for i in range(1, nb_labels):
            # 获取每个标签所对应的像素点的坐标
            indices = np.where(labels==i) 
            # 计算包围盒
            y_min = np.min(indices[0])
            y_max = np.max(indices[0])
            x_min = np.min(indices[1]) 
            x_max = np.max(indices[1])
            # 保存
            boxes.append(Block(Point(x_min,y_min),Point(x_max,y_max),self.get_bid()))      
        return boxes
    def get_crack_cluster(self):
        sorted_clusters=SortedList(key=lambda x: -x.area())
        rtree=index.Index()
        self.crack_cluster=[]
        clusters=[]
        for crack in self.cracks:
            blocks=crack.blocks
            viewport=crack.rect()
            feature=get_cluster_feature(blocks,viewport)
            clusters.append(Cluster(blocks,feature,viewport))
        # for overlapping_cluster in clusters:
        #     cv.imshow("tmp4",self.get_pixel_rect(overlapping_cluster.rect()).reshape(overlapping_cluster.rect().height,overlapping_cluster.rect().width)*255)
        #     cv.waitKey(0)
        is_merged=True
        # for i in self.blocks:
        #     if i.get_rect().area<0:
        #         print("?")
        #合并
        while is_merged==True:
            is_merged=False
            rtree=index.Index()
            sorted_clusters.clear()
            #构建cluster
            # print("构建cluster")
            for i,cluster in enumerate(clusters):
                rtree.insert(i,(cluster.rect().p1.x,cluster.rect().p1.y,cluster.rect().p2.x,cluster.rect().p2.y))
                blocks=cluster.blocks
                viewport=cluster.rect()
                feature=cluster.feature
                sorted_clusters.add(Cluster(blocks,feature,viewport))
            visit={i:True for i in sorted_clusters}
            # print("rtree size: ",rtree.get_size())
            #合并
            new_clusters=[]
            for cluster in sorted_clusters:
                merge_clusters=[]
                if visit[cluster]==True:
                    #查看是扩大后接触的
                    overlapping_clusters=[clusters[i] for i in rtree.intersection(get_tuple_rect(cluster.viewport.extend_abs((8,8))))]
                    for overlapping_cluster in overlapping_clusters:
                        # cv.imshow("tmp4",self.get_pixel_rect(overlapping_cluster.rect()).reshape(overlapping_cluster.rect().width,overlapping_cluster.rect().height)*255)
                        # cv.waitKey(0)
                        if visit[overlapping_cluster]==True:
                            merge_clusters.append(overlapping_cluster)
                    #合并
                    # print("合并",len(merge_clusters),"个cluster")
                    merged=None
                    for merge_cluster in merge_clusters:
                        if self.check_bridge(cluster.rect(),merge_cluster.rect())==True:
                            visit[merge_cluster]=False
                            if merged==None:
                                merged=merge_cluster
                            else:
                                is_merged=True
                                merged=merged.merge(merge_cluster)
                    new_clusters.append(merged)
            if len(new_clusters)!=0:
                print("done!，get",len(new_clusters),"cluster")
                clusters=new_clusters
        self.clusters=clusters
        
        pass
    def refine_crack(self,_cracks: List[Crack],ratio,min_Occupancy,min_size=4):
        # cracks=copy.deepcopy(cracks)
       
        def connect_nearest(block1:Block,block2:Block):
            block1=self.blocks[block1.bid]
            block2=self.blocks[block2.bid]
            near1=None
            near2=None
            if len(block1.sub_blocks)==0:
                near1=block1
                distance=None
                if len(block2.sub_blocks)==0:
                    near2=block2
                for sub_block in block2.sub_blocks:
                    sub_block=self.blocks[sub_block]
                    cur_dist=get_dist(near1.get_rect().center,sub_block.get_rect().center)
                    if distance==None:
                        distance=cur_dist
                        near2=sub_block
                    elif cur_dist<distance:
                        distance=cur_dist
                        near2=sub_block
            elif len(block2.sub_blocks)==0:
                near2=block2
                distance=None
                for sub_block in block1.sub_blocks:
                    sub_block=self.blocks[sub_block]
                    cur_dist=get_dist(near2.get_rect().center,sub_block.get_rect().center)
                    if distance==None:
                        distance=cur_dist
                        near1=sub_block
                    elif cur_dist<distance:
                        distance=cur_dist
                        near1=sub_block
            else :
                distance=None
                for _block1, _block2 in itertools.product(block1.sub_blocks,block2.sub_blocks):
                    _block1, _block2=self.blocks[_block1],self.blocks[_block2]
                    dist=get_dist(_block1.get_rect().center,_block2.get_rect().center)
                    if distance==None:
                        distance=dist
                        near1=_block1
                        near2=_block2
                    elif dist< distance:
                        distance=dist
                        near1=_block1
                        near2=_block2
                
            #connnect ,先随便连一下，后面如果需要用到方向信息再说，应该是用不到的
            block1.disconnect(block2.bid)
            block2.disconnect(block1.bid)
            near1.top_adj.append(near2.bid)
            near2.bottom_adj.append(near1.bid)
            return near1,near2
            
        def refine(raw_blocks:List[Block]):#双向扫描投影算法
            out_blocks=[]
            # print("****************")
            for block in raw_blocks:
                                    
                block=self.blocks[block.bid]
                # print("adj before op" ,len(block.get_adj()))
                rect=block.get_rect()
                total_sub_blocks=[]#一个block拆分后得到的全部block
                sub_refine_blocks=[]#承接各个分块中的不可分割block
                occupancu=self.get_Occupancy(rect)
                if occupancu<=0.1 and block.get_adj_num()==1:
                    #删除连接
                    for adj in block.get_adj():
                        self.blocks[adj].disconnect(block.bid)
                        self.blocks[block.bid].disconnect(adj)                    
                    continue
                if occupancu>min_Occupancy or min(rect.width,rect.height)<min_size:#不用继续细化的block
                    if occupancu!=0:
                        out_blocks.append(block)
                elif rect.width/rect.height>ratio:
                    # show_img(self.bin_img,rect,"out")
                    seg_num=rect.width//rect.height
                    seg_point=[int(i) for i in np.linspace(rect.p1.x,rect.p2.x,seg_num+1)]
                    segs=[(seg_point[i]+(1 if i!=0 else 0),seg_point[i+1]) for i in range(seg_num)]
                    intervals=[]
                    pre_blocks=[]#一个子块产生的block
                    
                    for seg in segs:
                        sub_blocks=[]
                        scan_line1=self.bin_img[rect.p1.y:rect.p2.y+1,seg[0]]
                        scan_line2=self.bin_img[rect.p1.y:rect.p2.y+1,seg[1]]
                        scan_line=np.stack([scan_line1,scan_line2],axis=0).transpose()
                        pre_pixel=0
                        for i,pixels in enumerate(scan_line):
                            for pixel in pixels:
                                if pre_pixel==0 and pixel==1:
                                    #找下界
                                    bottom=find_edge_vert(self.bin_img,seg[0],seg[1],rect.p1.y+i,-1,rect.p1.y,rect.p2.y)
                                    top=find_edge_vert(self.bin_img,seg[0],seg[1],rect.p1.y+i,1,rect.p1.y,rect.p2.y)
                                    if bottom>=top:
                                        pre_pixel=pixel
                                        continue
                                    if len(intervals)==0 or not istouch(intervals[-1],(bottom,top)):
                                        intervals.append((bottom,top))
                                    else :
                                        last_one=intervals.pop()
                                        intervals.append(merge(last_one,(bottom,top)))
                        #构建block
                        last_block=None
                        for interval in intervals:
                            new_block=Block(Point(seg[0],interval[0]),Point(seg[1],interval[1]),self.get_bid())
                            # print("insert vert:",seg[0],interval[0],seg[1],interval[1],"bid:" ,new_block.bid )
                            sub_blocks.append(new_block.bid)
                            self.blocks.append(new_block)
                            #检查上下连接
                            if last_block==None :
                                if self.get_Occupancy(new_block.get_rect())>0.1:
                                    last_block=new_block
                            else :
                                if get_bridge_rect(last_block,new_block).height<4 and self.get_Occupancy(new_block.get_rect())>0.1:#crack内部细化时可能导致断开，所以需要这个
                                    print("link internal vert",last_block.bid,new_block.bid)
                                    new_block.bottom_adj.append(last_block.bid)
                                    last_block.top_adj.append(new_block.bid)
                            #检查左右连接情况
                            if len(pre_blocks)!=0:
                                for pre_interval_bid in pre_blocks:
                                    pre_left_block=self.blocks[pre_interval_bid]
                                    pre_interval=pre_left_block.get_vert_range()
                                    if(istouch((interval[0]-1,interval[1]+1),pre_interval)):
                                        new_block.left_adj.append(pre_interval_bid)
                                        pre_left_block.right_adj.append(new_block.bid)
                            
                        total_sub_blocks.extend(sub_blocks)
                        pre_blocks=sub_blocks
                    #递归调用
                    sub_refine_blocks=refine([self.blocks[total_sub_block] for total_sub_block in total_sub_blocks])
                    out_blocks.extend(sub_refine_blocks)         
                
                else :#高长于宽，长宽正常，但是细化程度不够
                    seg_num=max(rect.height//rect.width,2)
                    seg_point=[int(i) for i in np.linspace(rect.p1.y,rect.p2.y,seg_num+1)]
                    segs=[(seg_point[i]+(1 if i!=0 else 0),seg_point[i+1]) for i in range(seg_num)]
                    intervals=[]
                    pre_blocks=[]
                    for seg in segs:
                        sub_blocks=[]
                        scan_line1=self.bin_img[seg[0],rect.p1.x:rect.p2.x+1]
                        scan_line2=self.bin_img[seg[1],rect.p1.x:rect.p2.x+1]
                        scan_line=np.stack([scan_line1,scan_line2],axis=0).transpose()
                        pre_pixel=0
                        for i,pixels in enumerate(scan_line):
                            for pixel in pixels:
                                if pre_pixel==0 and pixel==1:
                                    #找下界
                                    left=find_edge_hori(self.bin_img,seg[0],seg[1],rect.p1.x+i,-1,rect.p1.x,rect.p2.x)
                                    right=find_edge_hori(self.bin_img,seg[0],seg[1],rect.p1.x+i,1,rect.p1.x,rect.p2.x)
                                    if left>=right:
                                        pre_pixel=pixel
                                        continue
                                    if len(intervals)==0 or not istouch(intervals[-1],(left,right)):
                                        intervals.append((left,right))
                                    else :
                                        last_one=intervals.pop()
                                        intervals.append(merge(last_one,(left,right)))
                        #构建block
                        last_block=None
                        for interval in intervals:
                            new_block=Block(Point(interval[0],seg[0]),Point(interval[1],seg[1]),self.get_bid())
                            # print("insert hori:",interval[0],seg[0],interval[1],seg[1],"bid:" ,new_block.bid )
                            sub_blocks.append(new_block.bid)
                            self.blocks.append(new_block)
                            #检查左右连接
                            if last_block==None :
                                if self.get_Occupancy(new_block.get_rect())>0.1:
                                    last_block=new_block
                            else :
                                if get_bridge_rect(last_block,new_block).width<4 and self.get_Occupancy(new_block.get_rect())>0.1:#crack内部细化时可能导致断开，所以需要这个
                                    
                                    print("link internal hori",last_block.bid,new_block.bid)
                                    new_block.left_adj.append(last_block.bid)
                                    last_block.right_adj.append(new_block.bid)
                                    last_block=new_block
                            #检查上下连接情况
                            if len(pre_blocks)!=0:
                                for pre_interval_bid in pre_blocks:
                                    pre_bottom_block=self.blocks[pre_interval_bid]
                                    pre_interval=pre_bottom_block.get_hori_range()
                                    if(istouch((interval[0]-1,interval[1]+1),pre_interval)):
                                        new_block.bottom_adj.append(pre_interval_bid)
                                        pre_bottom_block.top_adj.append(new_block.bid)
                            
                        total_sub_blocks.extend(sub_blocks)
                        pre_blocks=sub_blocks
                    #递归调用
                    sub_refine_blocks=refine([self.blocks[total_sub_block] for total_sub_block in total_sub_blocks])
                    out_blocks.extend(sub_refine_blocks) 
                block.sub_blocks=[i.bid for i in sub_refine_blocks]
            #连接外层block(利用在subblock中的block)
            visit=[True for i in range(self.max_bid+1)]
            for raw_block in raw_blocks:
                # if raw_block.bid==127 or raw_block.bid==128:
                #     show_img(self.bin_img,raw_block.get_rect(),"test1")
                if visit[raw_block.bid]==True:
                    adjs=[self.blocks[bid] for bid in raw_block.get_adj()]    
                    # print("adj after op" ,raw_block.get_adj_num())#adj没有超过3的，所有的断点都是在adj超过3的，但是这里打印不出来，说没被删了，但是我没动过啊                
                    # if raw_block.get_adj_num()>2:
                    #     adjs.append(self.blocks[0])
                    for adj in adjs:#连接各个相邻的初始block
                        #找到两个block中最近的两个子block（当然adj本身可能就是不可分割的block）
                        if visit[adj.bid]==True:
                            connect_nearest(raw_block,adj)
                            pass
                    visit[raw_block.bid]=False
            # print("****************")   
            return out_blocks
        out=[]
        for _crack in _cracks:
            blocks=refine(_crack.blocks)
            out.append(Crack(blocks,self.get_cid(),_crack.bound))
        return out
        
            


    def extract_backbone(self):
        def connect(crack1:Crack,crack2:Crack):
            near1=None
            near2=None
            distance=None
            for _block1, _block2 in itertools.product(crack1.blocks,crack2.blocks):
                _block1, _block2=self.blocks[_block1.bid],self.blocks[_block2.bid]
                dist=get_dist(_block1.get_rect().center,_block2.get_rect().center)
                if distance==None:
                    distance=dist
                    near1=_block1
                    near2=_block2
                elif dist< distance:
                    distance=dist
                    near1=_block1
                    near2=_block2
            #connnect ,先随便连一下，后面如果需要用到方向信息再说，应该是用不到的
            near1.top_adj.append(near2.bid)
            near2.bottom_adj.append(near1.bid)
            return near1,near2
        self.backbones=[]
        # print("crack before merge： ", len(self.cracks))
        #fliter 
        filtered_cracks=[]
        cur_cid=self.max_cid
        for crack in self.cracks:
            if crack.cid>=cur_cid:
                break
            new_blocks=[]
            for block in crack.blocks:
                if self.get_Occupancy(block.get_rect())<0.1 and block.get_adj_num()==1:
                    print("filter")
                    for adj in block.get_adj():
                        self.blocks[adj].disconnect(block.bid)
                        self.blocks[block.bid].disconnect(adj)
                    continue
                new_blocks.append(block)
            new_crack=Crack(new_blocks,self.get_cid())
            filtered_cracks.append(new_crack)
            self.cracks.append(new_crack)
        sort_cracks=sorted(filtered_cracks ,key=lambda x :-x.rect().area)
        # sort_cracks=sorted(self.cracks ,key=lambda x :-x.rect().area)
        changed=True
        #crack之间连接
        while changed==True:
            changed=False
            new_cracks=[]
            rtree=index.Index()
            for crack in sort_cracks:
                rtree.insert(crack.cid,(crack.rect().p1.x,crack.rect().p1.y,crack.rect().p2.x,crack.rect().p2.y))
            visit=[True for i in range(self.max_cid+1)]
            for crack in sort_cracks:
                if visit[crack.cid]==True:
                    overlapping_cracks=[self.cracks[i] for i in rtree.intersection(get_tuple_rect(crack.rect().extend_abs((8,8))))]
                    merged=crack
                    for overlapping_crack in overlapping_cracks:
                        if not is_rectangle_overlap(crack.rect(),overlapping_crack.rect()) and self.check_bridge(crack.rect(),overlapping_crack.rect()):#合并断连的部分
                            connect(merged,overlapping_crack)
                            merged=merged.merge(overlapping_crack)
                            changed=True
                            visit[overlapping_crack.cid]=False
                    new_cracks.append(merged)
            sort_cracks=sorted(new_cracks ,key=lambda x :-x.rect().area)
        #test
        # print("crack after merge： ", len(sort_cracks))
        sort_cracks=self.refine_crack(sort_cracks,2,0.3)
        #crack内部连接

        for crack in sort_cracks:
            self.backbones.append(BackBone(crack.blocks))

    def extract_bifurcation_point(self):
        out=[]
        for backbone in self.backbones:
            for block in backbone.blocks:
                if block.get_adj_num()>2:
                    check=True
                    for i in block.get_adj():
                        if self.blocks[i].get_adj_num()==1:
                            check=False
                    if check:
                        out.append(block)
        return out

if __name__=="__main__":
    print("nothing")